package junior.DynamicProgramming动态规划;

/**
 * 确定状态，寻找状态转移方程
 * 最大子序列状态转移时，负数不予考虑（负数来源：过程中的最大子序列为负数）
 */
public class 最大子序和 {
    static int[] number = {-2,1,-3,4,-1,2,1,-5,4};
    public static void main(String[] args) {
        System.out.println("maxSub1："+maxSub(number));
        System.out.println("maxSub2："+maxSubOptimization1(number));
        System.out.println("maxSub2："+maxSubOptimization2(number));
    }
    // dp数组
    public static int maxSub(int[] number){
        int dp[]= new int[number.length];
        int max = dp[0];
        dp[0] = number[0];
        for (int i = 1; i < number.length; i++) {
            dp[i] = Math.max(dp[i-1],0) + number[i];
            max   = Math.max(dp[i],max);
        }
        return max;
    }
    public static int maxSubOptimization1(int[] number){
        int dp[]= new int[number.length];
        int max = dp[0];
        dp[0] = number[0];
        for (int i = 1; i < number.length; i++) {
            dp[i] = Math.max(dp[i-1],0) + number[i];
            max   = Math.max(dp[i],max);
        }
        return max;
    }
    // 优化dp数组，用一个变量temp代替（temp代替遍历过程中间dp[i-1]）
    public static int maxSubOptimization2(int[] a){
        int max = number[0],temp = number[0];
        for (int i = 1; i < number.length; i++) {
            temp = Math.max(temp,0) + number[i];
            max  = Math.max(temp,max);
        }
        return max;
    }
}
